package com.lw.leetcode.stack.b;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1856. 子数组最小乘积的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/16 20:12
 */
public class MaxSumMinProduct {


    public static void main(String[] args) {
        MaxSumMinProduct test = new MaxSumMinProduct();

        // 14
//        int[] arr = {1, 2, 3, 2};

        // 18
//        int[] arr = {2, 3, 3, 1, 2};

        // 66
//        int[] arr = {1, 2, 2, 4, 7, 3, 8, 2, 1, 1};

        // 60
//        int[] arr = {3, 1, 5, 6, 4, 2};

        // 36
//        int[] arr = {1, 2, 3, 4, 5};

        //
        int[] arr = Utils.getArr(100000, 1, 1000000);

        int i = test.maxSumMinProduct(arr);
        System.out.println(i);
    }

    public int maxSumMinProduct(int[] nums) {
        int length = nums.length;
        int[] arr1 = new int[length];
        long[] arr2 = new long[length];
        int index = -1;
        long sum = 0;
        for (int v : nums) {
            long s = 0;
            while (index != -1 && arr1[index] >= v) {
                s += arr2[index];
                sum = Math.max(sum, s * arr1[index]);
                index--;
            }
            index++;
            arr1[index] = v;
            arr2[index] = v + s;
        }
        long s = 0;
        while (index >= 0) {
            s += arr2[index];
            sum = Math.max(sum, s * arr1[index]);
            index--;
        }
        return (int) (sum % 1000000007);
    }

}
